562. Longest Line of Consecutive One in Matrix
Medium

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

 

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
Accepted
40.6K
Submissions
86.4K
Seen this question in a real interview before?
Companies
Show Hint 1
One solution is to count ones in each direction separately and find the longest line. Don't you think it will take too much lines of code?
Show Hint 2
Is it possible to use some extra space to make the solution simple?
Show Hint 3
Can we use dynamic programming to make use of intermediate results?
Show Hint 4
Think of a 3D array which can be used to store the longest line obtained so far for each direction.

Average Rating: 4.08 (26 votes)

Premium

Solution


Approach 1: Brute Force

Algorithm

The brute force approach is really simple. We directly traverse along every valid line in the given matrix: i.e. Horizontal, Vertical, Diagonal aline above and below the middle diagonal, Anti-diagonal line above and below the middle anti-diagonal. Each time during the traversal, we keep on incrementing the countcount if we encounter continuous 1's. We reset the countcount for any discontinuity encountered. While doing this, we also keep a track of the maximum countcount found so far.

Complexity Analysis

Let mm be the length of the matrix and nn be the width of the matrix. As a result, mnmn would be the total number of cells in the matrix.

  • Time complexity : O(mn)O(mn). We traverse along the entire matrix 4 times.
  • Space complexity : O(1)O(1). Constant space is used.

Approach 2: Using 3D Dynamic Programming

Algorithm

Instead of traversing over the same matrix multiple times, we can keep a track of the 1' along all the lines possible while traversing the matrix once only. In order to do so, we make use of a 4mn4mn sized dpdp array. Here, dp[0]dp[0], dp[1]dp[1], dp[2]dp[2] ,dp[3]dp[3] are used to store the maximum number of continuous 1's found so far along the Horizontal, Vertical, Diagonal and Anti-diagonal lines respectively. e.g. dp[i][j][0]dp[i][j][0] is used to store the number of continuous 1's found so far(till we reach the element M[i][j]M[i][j]), along the horizontal lines only.

Thus, we traverse the matrix MM in a row-wise fashion only but, keep updating the entries for every dpdp appropriately.

The following image shows the filled dpdp values for this matrix:

 0 1 1 0

 0 1 1 0
   
 0 0 1 1
   

Longest_Line

While filling up the dpdp, we can keep a track of the length of the longest consecutive line of 1's.

Watch this animation for complete process:

Current
1 / 14

Complexity Analysis

  • Time complexity : O(mn)O(mn). We traverse the entire matrix once only.

  • Space complexity : O(mn)O(mn). dpdp array of size 4mn4mn is used, where mm and nn are the number of rows ans coloumns of the matrix.


Approach 3: Using 2D Dynamic Programming

Algorithm

In the previous approach, we can observe that the current dpdp entry is dependent only on the entries of the just previous corresponding dpdp row. Thus, instead of maintaining a 2-D dpdp matrix for each kind of line of 1's possible, we can use a 1-d array for each one of them, and update the corresponding entries in the same row during each row's traversal. Taking this into account, the previous 3-D dpdp matrix shrinks to a 2-D dpdp matrix now. The rest of the procedure remains same as the previous approach.

Complexity Analysis

  • Time complexity : O(mn)O(mn). The entire matrix is traversed once only.

  • Space complexity : O(n)O(n). dpdp array of size 4n4n is used, where nn is the number of columns of the matrix.

Report Article Issue

Comments: 26
melodyincognito's avatar
Read More

Here is O(nm) solution by just using hash tables:

import collections
class Solution:
    def longestLine(self, M: List[List[int]]) -> int:
        row = collections.defaultdict(int)
        col = collections.defaultdict(int)
        ad = collections.defaultdict(int)  # Ascending diagonal
        dd = collections.defaultdict(int)  # Descending diagonal
        mx = 0
        for i in range(len(M)):
            for j in range(len(M[0])):
                if not M[i][j]:
                    row[i] = col[j] = ad[j + i] = dd [j - i] = 0
                else:
                    row[i] += 1
                    col[j] += 1
                    ad[j + i] += 1
                    dd[j - i] += 1
                    mx = max(mx, row[i], col[j], ad[j+i], dd[j-i])
        return mx

54
Show 4 replies
Reply
Share
Report
ashketchum's avatar
Read More

The Brute Force is giving better complexity than you Dynamic Programming approaches. Why should I solve the Dynamic programming approach over the brute force (technically)?

32
Show 7 replies
Reply
Share
Report
sean46's avatar
Read More

Could you add a comment on how the old/prev work to handle the diagonal case?

7
Reply
Share
Report
Pengwu550's avatar
Read More

the explaination for the third one is poor to understand

5
Show 2 replies
Reply
Share
Report
snidell's avatar
Read More

Why isnt this tagged DP if your solution is DP ? The array tag is practically useless on this platform

2
Reply
Share
Report
Ulfbert's avatar
Read More

Shouldn't approach 2 the same as approach 1 in term of time complexity?
You are going over the entire matrix once but at each element you are doing 4 times the amount of work compared to when you are going over an element in approach 1.

2
Reply
Share
Report
jessebrowne's avatar
Read More

There is no need to create an entire MxN matrix with the dynamic programming solution. You only need to keep the values from the previous row and the current row. You also only need three values (horizontal can be tracked using a single variable). Space is therefore only dependent on the size of a single row with 23N values (2 rows, 3 values per column).

1
Reply
Share
Report
rock1270's avatar
faangboy's avatar
Read More

It took me some while to understand the old and prev variables. Excellent optimized dp solution.

1
Reply
Share
Report
laosunhust's avatar
Read More

There is a O(mn) time O(1) space solution as well. check this out
https://discuss.leetcode.com/topic/87416/o-mn-time-no-extra-space-solution

1
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/26/2021 19:35Accepted96 ms39.5 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium